package org.liaohailong.victor;

import android.os.Build;

import androidx.annotation.RequiresApi;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * Author: liaohailong
 * Date: 2022/2/7
 * Time: 14:54
 * Description:
 **/
public class SortAndSearchStudy {

    // 颜色分类
    public static void sortColors(int[] nums) {
        if (nums.length < 1) return;

        // 0 红
        // 1 白
        // 2 蓝
        Map<Integer, Integer> priority = new HashMap<>();
        priority.put(0, 0);
        priority.put(1, 1);
        priority.put(2, 2);

        // 选择排序，找出最小的放左边 时间：On平方 空间：O1
        for (int i = 0; i < nums.length; i++) {
            for (int k = i + 1; k < nums.length; k++) {
                int curr = priority.get(nums[i]);
                int next = priority.get(nums[k]);
                if (next < curr) {
                    // 交换位置
                    nums[i] = nums[i] ^ nums[k];
                    nums[k] = nums[i] ^ nums[k];
                    nums[i] = nums[i] ^ nums[k];
                }
            }
        }

//        // 归并排序 时间：nLogN 空间：On
//        mergeSort(nums);
    }

    public static void mergeSort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1, new int[arr.length]);
    }

    public static void mergeSort(int[] arr, int i, int j, int[] temp) {
        if (i < j) {
            int mid = i + (j - i) / 2;
            mergeSort(arr, i, mid, temp);
            mergeSort(arr, mid + 1, j, temp);

            // 合并两个有序集合
            merge(arr, i, mid, j, temp);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left; // 第一个数组起始
        int j = mid + 1; // 第二个数组起始
        int k = 0; // 排序个数

        while (i <= mid || j <= right) {
            if (i <= mid && j <= right) {
                if (arr[i] < arr[j]) {
                    temp[k++] = arr[i++];
                } else {
                    temp[k++] = arr[j++];
                }
            } else if (i <= mid) {
                temp[k++] = arr[i++];
            } else if (j <= right) {
                temp[k++] = arr[j++];
            }
        }

        // 将temp数据拷贝到arr
        System.arraycopy(temp, 0, arr, left, k);
    }


    // 前 K 个高频元素
    @RequiresApi(api = Build.VERSION_CODES.N)
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> visitor = new HashMap<>();

        for (int num : nums) {
            Integer count = visitor.get(num);
            if (count == null) {
                count = 1;
            } else {
                count++;
            }
            visitor.put(num, count);
        }

        // 优先级排序队列
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> o2[1] - o1[1]);

        for (Map.Entry<Integer, Integer> entry : visitor.entrySet()) {
            Integer key = entry.getKey();
            Integer value = entry.getValue();
            queue.add(new int[]{key, value});
        }

        int[] arr = new int[k];
        for (int i = 0; i < arr.length; i++) {
            int key = queue.poll()[0];
            arr[i] = key;
        }
        return arr;
    }

    // 数组中的第K个最大元素
    @RequiresApi(api = Build.VERSION_CODES.N)
    public int findKthLargest(int[] nums, int k) {
        // 优先级排序队列
        Arrays.sort(nums);
        int index = nums.length - k;
        return nums[index];
    }

    // 寻找峰值
    public int findPeakElement(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }
        for (int i = 1; i < nums.length - 1; i++) {
            if (nums[i] > nums[i - 1] && nums[i + 1] < nums[i]) return i;
        }
        return nums[0] > nums[nums.length - 1] ? 0 : nums.length - 1;
    }

    // 在排序数组中查找元素的第一个和最后一个位置
    public int[] searchRange(int[] nums, int target) {
        if (nums.length < 1) return new int[]{-1, -1};
        int i = 0;
        int j = nums.length;
        while (i <= j) {
            if (j < 0 || i >= nums.length) break;
            int mid = i + (j - i) / 2;
            if (target < nums[mid]) {
                j = mid - 1;
            } else if (target > nums[mid]) {
                i = mid + 1;
            } else {
                // target == mid
                // 中心扩散法
                int k1 = mid;
                int k2 = mid;
                int val = nums[mid];
                boolean b1 = true, b2 = true;
                while (b1 || b2) {
                    if (k1 > 0 && val == nums[k1 - 1]) k1--;
                    else b1 = false;
                    if (k2 < nums.length - 1 && val == nums[k2 + 1]) k2++;
                    else b2 = false;
                }
                return new int[]{k1, k2};
            }
        }
        return new int[]{-1, -1};
    }

    // 合并区间
    public int[][] merge(int[][] intervals) {
        if (intervals.length < 2) return intervals;

        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);

        LinkedList<int[]> queue = new LinkedList<>();

        for (int[] curr : intervals) {
            if (queue.isEmpty()) {
                queue.addLast(curr);
            } else {
                int[] prev = queue.pollLast();
                if (curr[0] <= prev[1]) {
                    // 合并区间
                    int[] combined = new int[]{prev[0], Math.max(prev[1], curr[1])};

                    queue.addLast(combined);
                } else {
                    queue.addLast(prev);
                    queue.addLast(curr);
                }
            }
        }

        int[][] ints = new int[queue.size()][2];
        for (int i = 0; i < queue.size(); i++) {
            int[] node = queue.get(i);
            ints[i][0] = node[0];
            ints[i][1] = node[1];
        }

        return ints;
    }

    // 搜索旋转排序数组
    public int search(int[] nums, int target) {
        // 寻找k的位置
        int i = 0;
        int k = nums.length;
        while (true) {
            int mid = i + (k - i) / 2;
            if (nums[i] > nums[mid]) {
                k = mid;
            } else {
                i = mid;
            }
            // 找到k
            if (k - i <= 1) {
                // 未旋转
                if (k >= nums.length) {
                    k = 0;
                    break;
                }
                k = nums[i] > nums[k] ? i : k;
                break;
            }
        }

        int index = binarySearch(nums, 0, k, target);

        return index != -1 ? index : binarySearch(nums, k + 1, nums.length - 1, target);
    }

    private int binarySearch(int[] arr, int from, int to, int target) {
        while (from <= to) {
            if (to < 0 || from >= arr.length) return -1;
            int mid = from + (to - from) / 2;
            if (target > arr[mid]) {
                from = mid + 1;
            } else if (target < arr[mid]) {
                to = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }


    // 搜索二维矩阵 II
    public boolean searchMatrix(int[][] matrix, int target) {
        // 起始位置
        int x = matrix[0].length - 1;
        int y = 0;

        // PS: 斜线递增
        while (x >= 0 && y < matrix.length) {
            if (matrix[y][x] == target) {
                return true;
            } else if (matrix[y][x] > target) {
                x--;
            } else {
                y++;
            }
        }
        return false;
    }


}
